#!/usr/bin/env python3

"""
Given a binary tree and a sum, 
find all root-to-leaf paths where each path's sum equals to the given sum.
"""

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None



class Solution:
    def path_sum(self, root, sum):
        return [case for case in self.yield_path_sum_case(root, sum)]


    def yield_path_sum_case(self, root, sum):
        if root is None:
            return
        if root.left is None and root.right is None:
            if root.val == sum:
                yield [root.val]
            return
        
        for case in self.yield_path_sum_case(root.left, sum - root.val):
            case.insert(0, root.val)
            yield case

        for case in self.yield_path_sum_case(root.right, sum - root.val):
            case.insert(0, root.val)
            yield case
